#include <stdlib.h>
#include <limits.h>
#include "Tree.h"

#define NAO_ENCONTRADO -1

typedef HuffTree TipoItem;

typedef struct TipoNo {
	TipoItem item;
	struct TipoNo *prox;
} TipoNo;

typedef struct TipoLista {
	TipoNo *primeiro;
} *TipoLista;

TipoLista IniciaLista() {
	TipoLista L = malloc(sizeof(struct TipoLista));
	if(L != NULL) {
		L->primeiro = NULL;
	} /* se L == NULL não há mais memoria disponivel */

	return L;
}

void DestroiLista(TipoLista L) {
	TipoNo *p1 = L->primeiro;
	TipoNo *p2 = NULL;

	while(p1 != NULL) {
		p2 = p1;
		p1 = p1->prox;
		free(p2);
	}
	free(L);
}

void InserePrimeiroLista(TipoLista L, TipoItem elem) {
	TipoNo *P = malloc(sizeof(TipoNo));

	if(P == NULL) {
		printf("Erro: memoria cheia");
	} else {
		P->prox = L->primeiro;
		P->item = elem;
		L->primeiro = P;
	}
}

int ListaCheia(TipoLista L) {
	return 0;
}

int ListaVazia(TipoLista L) {
	if(L->primeiro == NULL) {
		return 1;
	} else {
		return 0;
	}
}

void InsereUltimoLista(TipoLista L, TipoItem elem) {
	TipoNo *P = malloc(sizeof(TipoNo));
	TipoNo *pAux;

	if(P == NULL) {
		printf("Erro: memoria cheia");
	} else {
		P->item = elem;
		P->prox = NULL;
		if(L->primeiro == NULL) { /* Lista vazia */
			L->primeiro = P;
		} else {
			pAux = L->primeiro;
			do {
				if(pAux->prox == NULL) {
					pAux->prox = P;
					pAux = NULL;
				} else {
					pAux = pAux->prox;
				}
			} while(pAux != NULL);
		}
	}
}

TipoItem PesquisaMinimo(TipoLista L, int *pos) {
	TipoNo* P = L->primeiro;
	int posAtual = 0, minfreq = INT_MAX, freq;
	HuffTree min;

	while((P != NULL)) {
		freq = GetFrequency(P->item);
		if(freq < minfreq) {
			min = P->item;
			minfreq = freq;
			*pos = posAtual++;
		} else {
			posAtual++;
		}
		P = P->prox;
	}

	return min;
}

void RemoveDeLista(TipoLista L, int pos) {
	TipoNo *P;
	TipoNo *anterior;
	int posAtual;

	if(L->primeiro == NULL) {
		printf("Erro: lista vazia"); /* Não é necessário */
		return;
	}
	if(pos == 0) {
		P = L->primeiro;
		L->primeiro = L->primeiro->prox;
	} else {
		P = L->primeiro->prox;
		anterior = L->primeiro;
		for(posAtual = 1; posAtual != pos; posAtual++) {
			anterior = P;
			P = P->prox;
		}
		anterior->prox = P->prox;
	}
	free(P);
}

TipoItem RecuperaDeLista(TipoLista L, int pos) {
	TipoNo *P;
	int posAtual;

	if(L->primeiro == NULL) {
		printf("Erro: lista vazia"); /* Não é necessário */
		return NULL;
	}
	P = L->primeiro;
	for(posAtual = 0; posAtual != pos; posAtual++) {
		P = P->prox;
	}
	return P->item;
}

int TamanhoLista(TipoLista L) {
	TipoNo *P = L->primeiro;
	int tamanho = 0;

	while(P != NULL) {
		P = P->prox;
		tamanho++;
	}
	return tamanho;
}


